package sort_1109;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Random;

public class Sort {
    /**
     * 快速排序
     *
     * 时间复杂度：
     * 最好情况：O(n * log(n))
     * 平均情况：O(n * log(n))
     * 最坏情况：O(n^2)
     *
     * 空间复杂度：
     * 最好情况：O(log(n))
     * 平均情况：O(log(n))
     * 最坏情况：O(n)
     *
     * 稳定性：不具备稳定性
     * @param array
     */
    public static void quickSort(long[] array) {
        // TODO: 具体实现代码见上节课的代码
        quickSortInternal(array, 0, array.length - 1);
    }

    private static void quickSortInternal(long[] array, int from, int to) {
        // 区间内的元素个数
        int size = to - from + 1;
        if (size <= 16) {
            insertSort(array, from, to);
            return;
        }

        // 三数取中法
        long leftValue = array[from];
        long rightValue = array[to];
        int midIdx = from + (to - from) / 2;
        long midValue = array[midIdx];

        if (leftValue <= rightValue) {
            if (rightValue <= midValue) {
                // rightValue 作为基准值
            } else if (leftValue <= midValue) {
                // midValue
                swap(array, midIdx, to);
            } else {
                // leftValue
                swap(array, from, to);
            }
        } else {
            // leftValue > rightValue
            if (leftValue <= midValue) {
                // leftValue
                swap(array, from, to);
            } else if (midValue <= rightValue) {
                // rightValue
            } else {
                // midValue
                swap(array, midIdx, to);
            }
        }

        int i = partition(array, from, to);

        quickSortInternal(array, from, i - 1);
        quickSortInternal(array, i + 1, to);
    }

    private static int partition(long[] array, int from, int to) {
        long pivot = array[to];
        int left = from;
        int right = to;

        while (left < right) {
            while (left < right && array[left] <= pivot) {
                left++;
            }

            array[right] = array[left];

            while (left < right && array[right] >= pivot) {
                right--;
            }

            array[left] = array[right];
        }

        array[left] = pivot;

        return left;
    }

    private static void swap(long[] array, int i, int j) {
        long t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    private static void insertSort(long[] array, int from, int to) {
        int size = to - from + 1;
        for (int i = 1; i < size; i++) {
            // 有序区间 [from, from + i)
            // 无序区间的第一个元素的下标 [from + i]
            long x = array[from + i];

            // 遍历有序区间
            int j;
            for (j = from + i - 1; j >= from && array[j] > x; j--) {
                array[j + 1] = array[j];
            }

            array[j + 1] = x;
        }
    }

    public static void main2(String[] args) {
        long[] array = new long[1000_0000];
        Random random = new Random();
        for (int i = 0; i < 1000_0000; i++) {
            array[i] = random.nextInt();
        }

        long[] copy = Arrays.copyOf(array, array.length);

        mergeSort(array);
        Arrays.sort(copy);

        System.out.println(Arrays.equals(copy, array));
    }

    public static void main1(String[] args) {
        long[] array = { 9, 5, 1, 0, 3, 8, 2, 4, 6 };
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 归并排序
     *
     * 时间复杂度：
     * 最好/平均/最坏： O(n * log(n))
     *
     * 空间复杂度：
     * 最好/平均/最坏： O(n)
     *
     * 稳定型：具备稳定性
     * @param array
     */
    public static void mergeSort(long[] array) {
        mergeSortInternal(array, 0, array.length);
    }

    // 待排序区间：[from, to)
    private static void mergeSortInternal(long[] array, int from, int to) {
        if (to <= 1 + from) {
            return;
        }

        // 把待排序区间对半分开
        // 找到中间位置下标
        int mid = from + (to - from) / 2;
        // 整个区间被切割成
        // [from, mid)
        // [mid, to)
        // 按照相同的方式，先把左右两个区间变得有序
        mergeSortInternal(array, from, mid);
        mergeSortInternal(array, mid, to);

        // [from, mid)   有序了
        // [mid, to)     有序了

        merge(array, from, mid, to);
    }

    private static void merge(long[] array, int from, int mid, int to) {
        int size = to - from;
        // 需要的额外空间
        long[] e = new long[size];
        int eIdx = 0;

        int leftIdx = from; // 左边区间要处理的元素的下标
        int rightIdx = mid; // 右边区间要处理的元素的下标
        // 什么条件表示左边区间 [from, mid) 就没有元素了   leftIdx == mid
        // 同理右边区间：rightIdx == to
        // 两个区间都有元素的时候才要比较
        // 左区间有元素：leftIdx < mid
        // 右: rightIdx < to
        // leftIdx < mid && rightIdx < to
        while (leftIdx < mid && rightIdx < to) {
            // 要比较的两个元素 array[leftIdx] 和 array[rightIdx]
            if (array[leftIdx] <= array[rightIdx]) {
                // 取左边的元素放入 e 数组
                e[eIdx] = array[leftIdx];
                eIdx++;
                leftIdx++;
            } else {
                // 取右边的元素放入 e 数组
                e[eIdx] = array[rightIdx];
                eIdx++;
                rightIdx++;
            }
        }

        // 说明有一个区间的元素被全部取完了
        if (leftIdx < mid) {
            // 右边取完了，把左边的所有元素依次放到 e 中
            while (leftIdx < mid) {
                e[eIdx] = array[leftIdx];
                eIdx++;
                leftIdx++;
            }
        } else {
            while (rightIdx < to) {
                e[eIdx] = array[rightIdx];
                eIdx++;
                rightIdx++;
            }
        }

        // e 里是有序的 [0, size)
        // 要把有序的元素从 e 中搬回到 array 中 [from, to)

        for (int i = 0; i < size; i++) {
            array[from + i] = e[i];
        }
    }

    public static void mergeSort2(long[] array) {
        long[] e = new long[array.length];
        mergeSortInternal2(array, 0, array.length, e);
    }
    private static void mergeSortInternal2(long[] array, int from, int to, long[] e) {
        if (to <= 1 + from) {
            return;
        }

        // 把待排序区间对半分开
        // 找到中间位置下标
        int mid = from + (to - from) / 2;
        // 整个区间被切割成
        // [from, mid)
        // [mid, to)
        // 按照相同的方式，先把左右两个区间变得有序
        mergeSortInternal2(array, from, mid, e);
        mergeSortInternal2(array, mid, to, e);

        // [from, mid)   有序了
        // [mid, to)     有序了

        merge2(array, from, mid, to, e);
    }

    private static void merge2(long[] array, int from, int mid, int to, long[] e) {
        int size = to - from;
        int eIdx = 0;

        int leftIdx = from; // 左边区间要处理的元素的下标
        int rightIdx = mid; // 右边区间要处理的元素的下标
        // 什么条件表示左边区间 [from, mid) 就没有元素了   leftIdx == mid
        // 同理右边区间：rightIdx == to
        // 两个区间都有元素的时候才要比较
        // 左区间有元素：leftIdx < mid
        // 右: rightIdx < to
        // leftIdx < mid && rightIdx < to
        while (leftIdx < mid && rightIdx < to) {
            // 要比较的两个元素 array[leftIdx] 和 array[rightIdx]
            if (array[leftIdx] <= array[rightIdx]) {
                // 取左边的元素放入 e 数组
                e[eIdx] = array[leftIdx];
                eIdx++;
                leftIdx++;
            } else {
                // 取右边的元素放入 e 数组
                e[eIdx] = array[rightIdx];
                eIdx++;
                rightIdx++;
            }
        }

        // 说明有一个区间的元素被全部取完了
        if (leftIdx < mid) {
            // 右边取完了，把左边的所有元素依次放到 e 中
            while (leftIdx < mid) {
                e[eIdx] = array[leftIdx];
                eIdx++;
                leftIdx++;
            }
        } else {
            while (rightIdx < to) {
                e[eIdx] = array[rightIdx];
                eIdx++;
                rightIdx++;
            }
        }

        // e 里是有序的 [0, size)
        // 要把有序的元素从 e 中搬回到 array 中 [from, to)

        for (int i = 0; i < size; i++) {
            array[from + i] = e[i];
        }
    }

    public static void mergeSort非递归版本(long[] array) {
        long[] e = new long[array.length];

        // i 个元素和 i 个元素要归并
        for (int i = 1; i < array.length; i *= 2) { // Log(n)
            // 内部的循环代表，代表一组一组完成归并
            for (int j = 0; j < array.length; j += (2 * i)) {   // O(n)
                int from = j;
                int mid = from + i;
                if (mid >= array.length) {
                    // 说明没有右边的区间，本次不需要处理了
                    break;
                }
                int to = mid + i;
                if (to > array.length) {
                    to = array.length;
                }

                merge2(array, from, mid, to, e);
            }
        }
    }

    public static void quickSort非递归(long[] array) {
        Deque<Integer> stack = new LinkedList<>();
        // 一开始就把待排序区间放入
        stack.push(0);
        stack.push(array.length - 1);

        while (!stack.isEmpty()) {
            int to = stack.pop();
            int from = stack.pop();
            if (to - from + 1 <= 1) {
                continue;
            }

            int i = partition(array, from, to);

            stack.push(from);
            stack.push(i - 1);

            stack.push(i + 1);
            stack.push(to);
        }
    }

    public static void main(String[] args) {
        long[] array = { 9, 5, 1, 7, 2, 8, 3, 6, 0, 4 };
        quickSort非递归(array);
        System.out.println(Arrays.toString(array));
//        long[] array = {1, 2, 3};
//        Arrays.sort(array);     // 基本类型使用快排
//
//        Integer[] a = { 1, 2, 3 };
//        Arrays.sort(a);         // 引用类型用了归并
    }
}
